﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace 数据结构课设_电文的编码与译码_CSharp
{
    class Huffman
    {
        Node huffmantree = null;
        Node huffmandictionary = null;
        Node now_least_node=null,now_less_node = null;
        public Huffman() { }

        public Huffman(Node node)
        {
            huffmantree = node;
        }
        /// <summary>
        /// 获得权值最小的两个码
        /// </summary>
        public void GetWeightArray()
        {
            Node link=null,temp=null, root_node=null, least_node = null, less_node= null;//临时存储当前节点,第一最小值,第二最小值
            link = huffmantree;
            //设置当前查找的根node
            root_node = link;
            //查找第一个最小权值
            while (true)
            {
                //选取最上层节点,只循环无LNode的node
                while (true)
                {
                    if (link.LChild == null)
                    {
                        if (link.RChild != null)
                        {
                            link = link.RChild;
                        }
                        else
                        {
                            temp = link;
                            break;
                        }
                    }
                    else
                    {
                        temp = null;
                        break;
                    }
                }
                if (temp != null)
                {
                    //判断temp1是否有
                    if (least_node == null)
                    {
                        least_node = temp;
                    }
                    else if (temp.Weight < least_node.Weight)
                    {
                        less_node = least_node;
                        least_node = temp;
                    }
                    else if (less_node == null)
                    {
                        less_node = temp;
                    }
                    else if (temp.Weight < less_node.Weight)
                    {
                        less_node = temp;
                    }
                }
                //移动到下一个node
                root_node = root_node.Next;
                //判断是否到达最后一个node
                if (root_node == null) {
                    //对最小的两个值进行赋值
                    now_least_node = least_node;
                    now_less_node = less_node;
                    break;
                }
                link = root_node;
            }
            return; 
        }

        /// <summary>
        /// 构建huffman树
        /// </summary>
        public void CreateHuffmanTree()
        {
            while(true)
            {
                GetWeightArray();
                if (now_less_node == null)
                {

                    break;
                }
                now_least_node.RChild = new Node(now_least_node.Weight+ now_less_node.Weight);
                now_less_node.LChild = now_least_node.RChild;
            }
        }

        /// <summary>
        /// 构建huffman字典
        /// </summary>
        public void CreateHuffmanDictionary()
        {
            Node link = null,link_child=null,temp=null;
            String str_temp_code="";
            link = huffmantree;
            while (true)
            {
                temp = null;
                str_temp_code = "";
                link_child = link;
                //反向赋值
                while (true)
                {
                    if (link_child.RChild != null)
                    {
                        str_temp_code = "0" + str_temp_code;
                        link_child = link_child.RChild;
                    }
                    else if (link_child.LChild != null)
                    {
                        str_temp_code = "1" + str_temp_code;
                        link_child = link_child.LChild;
                    }
                    else
                    {
                        break;
                    }
                }
                temp = new Node(link.Key, str_temp_code);
                if (huffmandictionary == null)
                {
                    huffmandictionary = temp;
                }
                else
                {
                    huffmandictionary.Previous = temp;
                    temp.Next = huffmandictionary;
                    huffmandictionary = temp;
                }
                link =link.Next;
                if (link == null)
                {
                    break;
                }
            }
        }

        /// <summary>
        /// 获取huffman字典
        /// </summary>
        public Node getHuffmanDictionary()
        {
            return huffmandictionary;
        }
    }
}
